package _0_2_背包问题

/*
*
卡码网题意链接:
https://kamacoder.com/problempage.php?pid=1046

代码随想录 动态规划章节
0-1背包问题  一维数组解法

题意:

	有 n 件物品, 和一个最多能背重量为 w 的背包.
	第 i 件物品的重量为weight[i], 得到的价值是value[i].
	每件物品只能用一次.

	求解将哪些物品装入背包, 总价值最大?

例如物品和背包信息如下:
物品列表:

	重量		价值

物品0	1		15
物品1	3		20
物品2	4		30

当前背包最大容量为4

思路:
对于背包问题其实状态都是可以压缩的.
在使用二维数组解法时:	dp[i][j] = { dp[i-1][j]

	{ dp[i-1][j-weight[i]] + value[i]

与其把dp[i-1]这一层拷贝到dp[i]上, 不如只用一个一维数组, 只用dp[j] (然后进行i次赋值)
这就是滚动数组的由来, 需要满足的条件是上一层可以重复利用, 直接拷贝到当前层

一. dp[j]含义

	dp[j]: 背包容量为j时, 所能装的最大价值

二. 递推公式:

	dp[j] = { dp[j]
			{ dp[j-weight[i]] + value[i])

三. 初始化

	dp[0]=0  dp[j]表示容量为j的背包能装多大的价值, 容量为0装个屁, 价值为0
	其它非0下标初始化为0即可, 题目给的价值都是正整数, 0就是最小值了

横坐标: 第i个物品
纵坐标: 装j重量的背包

	0		1		2		3		4      重量

物品0	0		15		0		0		0

四. 遍历dp

	二维dp的写法, 遍历背包的顺序是不一样的!
	二维dp遍历的时候, 背包容量是从小到大, 而一维dp遍历时, 背包需要从大到小遍历

	原因:
		倒序遍历是为了保证物品i只被放入一次!	如果正序遍历, 物品0就会被重复加入多次!

举个例子: 物品0的重量weight[0]=1, 价值vaLue[0]=15

如果正序遍历
dp[1] = dp[1-weight[0]] + value[0]

	= dp[0]+15 = 15

dp[2] = dp[2-weight[0]] + value[0] = 30

	= dp[1] + 15 = 30
*/
func test_2_wei_bag_problem(weight, value []int, bagWeight int) int {
	// 定义 and 初始化
	dp := make([]int, bagWeight+1)
	// 递推顺序
	for i := 0; i < len(weight); i++ {
		// 这里必须倒序,区别二维,因为二维dp保存了i的状态
		for j := bagWeight; j >= weight[i]; j-- {
			// 递推公式
			dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
		}
	}
	//fmt.Println(dp)
	return dp[bagWeight]
}
